package com.cqs.leetcode.dp;

import com.google.common.collect.Lists;

import java.util.ArrayList;
import java.util.List;

class StockSpanner {

    final static int MAX_SIZE = 10000;
    private int[] prices = new int[MAX_SIZE];
    private int[] dp = new int[MAX_SIZE];
    int size = -1;

    public StockSpanner() {

    }

    public int next(int price) {
        this.prices[++size] = price;
        return dp[size] = dfs(price, size - 1, 0) + 1;
    }


    private int dfs(int price, int idx, int cnt) {
        if (idx < 0 || prices[idx] > price) return cnt;
        if (prices[idx] == price) return dp[idx] + cnt;
        int nextIdx = idx - dp[idx];
        return dfs(price, nextIdx, dp[idx]) + cnt;
    }

    public static void main(String[] args) {
        List<List<Integer>> cases = new ArrayList<>();
        cases.add(Lists.newArrayList(100, 80, 60, 70, 60, 75, 85));
        for (List<Integer> arr : cases) {
            StockSpanner stockSpanner = new StockSpanner();
            System.out.print(" input: " + arr + "\t");
            for (Integer integer : arr) {
                int next = stockSpanner.next(integer);
                System.out.print(next + "\t");
            }
            System.out.println();
        }

    }

}